package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 461. 汉明距离
 * @date 2025/2/17 13:27
 */
public class E461 {

    /**
     * <h3>方法一：异或平移法，平移到个位看是不是1</h3>
     *
     * @param x x
     * @param y y
     * @return 汉明距离
     */
    public int hammingDistance1(int x, int y) {
        int xor = x ^ y;
        int count = 0;
        while (xor > 0) {
            // 逐位平移检查
            if ((xor & 1) == 1) count++;
            xor >>= 1;
        }
        return count;
    }

    /**
     * <h3>方法二：Integer类</h3>
     *
     * @param x x
     * @param y y
     * @return 汉明距离
     */
    public int hammingDistance2(int x, int y) {
        return Integer.bitCount(x ^ y);
    }

    /**
     * <h3>方法三：位运算，用与运算每次去掉最低位的1</h3>
     *
     * @param x x
     * @param y y
     * @return 汉明距离
     */
    public int hammingDistance3(int x, int y) {
        int xor = x ^ y;
        int count = 0;
        while (xor > 0) {
            count++;
            // 每次去掉最低位的1
            // xor - 1的结果就是原来最后一个1及以后按位取反
            xor = xor & (xor - 1);
        }
        return count;
    }

    /**
     * <h3>方法四：位运算，分治法，Integer包装类方法bitCount的原理</h3>
     *
     * @param x x
     * @param y y
     * @return 汉明距离
     */
    public int hammingDistance4(int x, int y) {
        int xor = x ^ y;
        // 将相邻的两位相加，得到每两位中的 1 的数量
        xor = xor - ((xor >>> 1) & 0x55555555);
        // 将相邻的四位相加，得到每四位中的 1 的数量。
        xor = (xor & 0x33333333) + ((xor >>> 2) & 0x33333333);
        // 将相邻的八位相加，得到每四位中的 1 的数量。
        xor = (xor + (xor >>> 4)) & 0x0F0F0F0F;
        // 将相邻的十六位相加，得到每四位中的 1 的数量。
        xor = (xor + (xor >>> 8)) & 0x00FF00FF;
        // 将整个 32 位相加，得到每四位中的 1 的数量。
        xor = (xor + (xor >>> 16)) & 0x0000FFFF;
        return xor;
    }
}
